#include <stdio.h>
#include <stdlib.h>

// 树结点结构
typedef struct TreeNode
{
    int data;
    struct TreeNode *firstChild;  // 第一个孩子结点
    struct TreeNode *nextSibling; // 下一个兄弟结点
} TreeNode;

// 二叉树结点结构
typedef struct BinaryTreeNode
{
    int data;
    struct BinaryTreeNode *left;  // 左孩子
    struct BinaryTreeNode *right; // 右孩子
} BinaryTreeNode;

// 创建树结点
TreeNode *createTreeNode(int data)
{
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;
    return newNode;
}

// 创建二叉树结点
BinaryTreeNode *createBinaryTreeNode(int data)
{
    BinaryTreeNode *newNode = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 将森林转换为二叉树
BinaryTreeNode *convertForestToBinaryTree(TreeNode *forest[], int treeCount)
{
    if (treeCount == 0)
    {
        return NULL;
    }

    // 处理第一棵树
    BinaryTreeNode *binaryRoot = createBinaryTreeNode(forest[0]->data);

    // 递归处理第一棵树的子树
    if (forest[0]->firstChild != NULL)
    {
        TreeNode *childNodes[100]; // 假设最多100个子结点
        int childCount = 0;
        TreeNode *child = forest[0]->firstChild;

        while (child != NULL)
        {
            childNodes[childCount++] = child;
            child = child->nextSibling;
        }

        binaryRoot->left = convertForestToBinaryTree(childNodes, childCount);
    }

    // 处理森林中的其他树（作为右子树）
    if (treeCount > 1)
    {
        binaryRoot->right = convertForestToBinaryTree(forest + 1, treeCount - 1);
    }

    return binaryRoot;
}

// 打印森林（前序遍历）
void printForest(TreeNode *forest[], int treeCount)
{
    for (int i = 0; i < treeCount; i++)
    {
        printf("Tree %d: ", i + 1); // 打印树编号
        TreeNode *root = forest[i];

        // 使用栈进行前序遍历
        TreeNode *stack[100];
        int top = -1;

        if (root != NULL)
        {
            stack[++top] = root;
        }

        while (top >= 0)
        {
            TreeNode *node = stack[top--];
            printf("%d ", node->data); // 打印结点数据

            // 将子结点逆序压入栈中
            TreeNode *child = node->firstChild;
            while (child != NULL)
            {
                stack[++top] = child;
                child = child->nextSibling;
            }
        }

        printf("\n");
    }
}

// 打印二叉树（前序遍历）
void printBinaryTree(BinaryTreeNode *root)
{
    if (root != NULL)
    {
        printf("%d ", root->data); // 打印结点数据
        printBinaryTree(root->left);
        printBinaryTree(root->right);
    }
}

int main()
{
    // 创建三棵树组成的森林

    // 第一棵树: 1
    //         /|\
    //        2 3 4
    //       / \
    //      5   6
    TreeNode *tree1 = createTreeNode(1);
    tree1->firstChild = createTreeNode(2);
    tree1->firstChild->nextSibling = createTreeNode(3);
    tree1->firstChild->nextSibling->nextSibling = createTreeNode(4);
    tree1->firstChild->firstChild = createTreeNode(5);
    tree1->firstChild->firstChild->nextSibling = createTreeNode(6);

    // 第二棵树: 7
    //         / \
    //        8   9
    TreeNode *tree2 = createTreeNode(7);
    tree2->firstChild = createTreeNode(8);
    tree2->firstChild->nextSibling = createTreeNode(9);

    // 第三棵树: 10
    //          |
    //          11
    TreeNode *tree3 = createTreeNode(10);
    tree3->firstChild = createTreeNode(11);

    // 将树放入森林数组
    TreeNode *forest[3] = {tree1, tree2, tree3};

    printf("Original forest:\n"); // 原始森林
    printForest(forest, 3);

    // 将森林转换为二叉树
    BinaryTreeNode *binaryTree = convertForestToBinaryTree(forest, 3);

    printf("\nConverted binary tree (preorder): "); // 转换后的二叉树（前序遍历）
    printBinaryTree(binaryTree);
    printf("\n");

    return 0;
}